The present invention relates to a device and method of detecting motion vectors. More particularly, the present invention relates to a technique of decreasing computational complexity for motion vector detection and realizing proper motion vector detection.
The motion compensated inter-frame prediction system using block matching operations has been standardized and widely used as a technique of efficiently encoding motion image data. The interframe prediction requires to detect motion vectors. In order to capture large motion vectors, the vector value of a motion vector must be widely searched. However, a wide search range of motion vectors leads to the enormous computation for the matching process, thus causing the disadvantage in enlarging the system scale and in making the real-time processing difficult.
In order to deal with such problems, JP-A No. 166684/1989 (hereinafter referred to as a prior art 1) discloses a motion vector detection device while JP-A No. 328333/1993 (hereinafter referred to as a prior art 2) discloses a motion vector detection device.
FIG. 19 is a block diagram illustrating the configuration of the motion vector detecting device according to the prior art 1. In the motion vector detection device, the frame memory 201 stores reference image data. The reference point setting section 202 sets reference points referred to according to the search motion vector by using the reference image data stored in the frame memory 201 based on an offset set by the horizontal offset control section 206 and an offset set by the vertical offset control section 207. The subtracting section 203 obtains a difference between input data and a reference point. The frame difference addition section 204 sums differential data sets being output results from the differential section 203. The minimum value detection section 205 detects a minimum value of the sum and then detects a motion vector to provide a horizontal motion vector component Vx and a vertical motion vector component Vy. The adding section 210 adds an offset value selected by the selector 208 to the motion vector horizontal component Vx from the minimum value detection section 205. The adding section 211 adds an offset value selected by the selector 209 to the motion vector horizontal component Vy from the minimum value detection section 205. Thus, the final motion vector (horizontal motion vector component and vertical motion vector component) is computed. The horizontal offset control section 206 sets an offset value for motion vector search in the next frame by the horizontal component Vx of a motion vector from the minimum value detection section 205. The vertical offset control section 207 sets an offset value for motion vector search in the next frame by the vertical component Vy of a motion vector from the minimum value detection section 205.
In the offset setting operation of the horizontal offset control section 206 and the vertical offset control section 207, one motion vector component is expressed by the following formula:
xcex4V(n+1)=xcex4V(n)+(xcex1xc3x97xcex94V)
where xcex4V(n) is the offset value of the n-th frame; and xcex94V is a search range. One component V of a motion vector is expressed by the range satisfying xe2x88x92Vxe2x89xa6Vxe2x89xa6xcex94V. The value of xcex1 is expressed the formula of xcex1=1 (V=xcex94V), xcex1=xe2x88x921 (V=xcex94V), or xcex1=0 (Vxe2x89xa0xcex94, xe2x88x92xcex94V)).
FIG. 20 is a block diagram illustrating the configuration of the motion vector detecting device according to the prior art 2. In the motion vector detection device, the motion vector detection circuit 301 detects a motion vector providing a minimum prediction error based on image data for an input current frame and reference image data over a search range of specified by the selector 304. The motion vector memory 302 stores the detected motion vector for the duration of one frame and then outputs it as a motion vector at the same position on the previous frame to the search range decision section 303.
The search range decision section 303 judges the search range of motion vectors in a target block within the current frame according to the magnitude and direction of the motion vector of the previous frame. The selector 304 selectively outputs one of N search ranges ranging from the first search range to the n-th search range according to decision results of the search range decision section 303. The motion vector detection circuit 301 searches motion vectors over a selected search range.
In addition to the normal search range shown in FIG. 21(a), the selector 304 outputs the search range attaching importance to the horizontal direction as shown in FIG. 21(b), the search range attaching importance to the vertical direction as shown in FIG. 21(c), or the search range attaching importance to the slanting direction as shown in FIG. 21(d). The search range attaching importance to the horizontal direction as shown in FIG. 22(b) and the search range attaching importance to the vertical direction as shown in FIG. 22(c) can be used as a modified search range, in addition to the normal search range shown in FIG. 22(a)
However, the prior arts 1 and 2 have the following drawbacks:
In the prior art 1, the search range cannot be followed under an occurrence condition of some motion vectors so that the optimum search range of motion vectors cannot be covered. As a consequence, the prior art 1 cannot suitably detect motion vectors.
The prior art 2 has a disadvantage in that the motion vector cannot be suitably detected because only limited types of search range can be selected. Moreover, since the search range over a motion boundary portion is often predicted erroneously, the motion vector cannot be suitably detected.
As a related art, JP-A-No. 30407/1993 (hereinafter referred to as prior art 3) discloses a motion vector detection technique for realizing the automatic mechanism such as autofocus, autoiris or the like for cameras.
In the prior art 3, a partial physical region in the image pickup region 401 acts as the motion vector detection region 403 for motion vector detection, as shown in FIG. 23.
The motion vector detection region 403 is divided into plural sub-divided regions 404 to create a histogram showing vector values of motion vectors detected for the sub-divided regions 404. The motion vector detection region 403 on the next frame is decided by setting the motion vector with the highest occurrence frequency on the histogram as the motion vector of the subject 402.
However, the process ranging from creation of a histogram to the computation of the motion vector detection region 403 on the next frame is realized by software. Hence, where the method is applied to encode motion images needed to detect motion vectors of the whole image region within one frame, a sophisticated processing circuit such as processor or microprocessor with considerable high processing capability is required.
When an image contains a still portion, the occurrence frequency of (0, 0)in a detected motion vector becomes high. However, in the prior art 3, since a correction process is not performed to motion vectors with high occurrence frequency at (0, 0), the motion vector detection region 403 may not be suitably set according to the motion of the subject 402.
Moreover, since the same matching process must be performed for motion vector detection, regardless the degree of the motion of the subject 402, the computational complexity for the matching process becomes enormous to capture a specially large motion vector.
The present invention is made to solve the above-mentioned problems. The objective of the present invention is to provide a motion vector detection device that can reduce the computational complexity by limiting the range searching for the vector values of a motion vector for, particularly, motion image encoding applications and can suitably detect motion vectors by setting an optimum search range.
Another objective of the present invention is to provide a motion vector detection method that can reduce the computational complexity by limiting the range searching for the vector values of a motion vector for, particularly, motion image encoding applications and can suitably detect motion vectors by setting an optimum search range.
The objective of the present invention is achieved by a motion vector detection device comprising motion vector detection means for dividing image data on a current frame into predetermined regions, matching the image data on the current frame with reference image data every divided region, and detecting motion vectors with vector values within a search range externally indicated; motion vector frequency storage means for classifying the motion vectors within each divided region detected by the motion vector detection means under the vector value range and then storing the number of the motion vectors; and indication means for indicating a search range of vector values of a motion vector to be detected by the motion vector detection mean, based on the number of the motion vectors classified and stored by the motion vector frequency storage means.
In the motion vector detection device, the motion vector frequency storage means classifies the number of vector values of a motion vector detected by the motion vector detection means and stores the classified data in the form of, for example, a histogram. The motion vector detection device can be indicated a search range of vector values of a motion vector according to the histogram. That is, when the motion of a subject is uniform, the image data of a motion image has a localization in the vector value of a motion vector. Hence, the motion vector detection can be suitably performed by indicating a search range of vector values of a motion vector to be detected in the next frame according to the vector value of a motion vector detected in the image data for the previous frame. Moreover, since the vector value of a motion vector to be detected is limited, the computational complexity which is required in a matching process where the motion vector detection means detects the motion vector can be reduced. In the motion vector detection, the motion vector frequency storage means classifies motion vectors within each divided region detected by the motion vector detection means so as to contain the vector values of plural motion vectors within one range and then stores the number of the motion vectors.
In this case, one range in the histogram contains plural vector values. Hence, the motion vector frequency storage means is not required to have a storage capacity corresponding to the number of vector values of a motion vector contained within the search range, so that the storage capacity can be saved.
The motion vector detection device m ay further comprises storage control means for incrementing the number corresponding to a range containing the detected vector value among motion vector numbers stored in the motion vector frequency storage means every time the motion vector detection means detects the vector value of a motion vector in each of each divided region.
In the motion vector detection device, the indication means indicates the motion vector search range so as to center a vector value corresponding to the maximum number among the motion vector numbers classified and stored by the motion vector frequency storage means.
In this case, where there are plural classifications each which contains the greatest number of motion vectors, the search range of vector values of the motion vector may be indicated so as to center the vector value corresponding to the barycentric position of them.
In the motion vector detection device, the indication means indicates a motion vector search range based on a number with numbers larger than a predetermined threshold value among the motion vector numbers classified and stored in the motion vector frequency storage means.
In this case, in the classification where vector values of a motion vector detected by the motion vector detection means exceed a predetermined threshold, it is not needed to store numbers exceeding the number of the corresponding vector values. Thus, the bit number to store the number of motion vectors detected every classification can be reduced so that the storage capacity of the motion vector frequency storage means can be reduced.
The motion vector detection device further comprises correction means for correcting a motion vector number stored in the motion vector frequency storage means. The indication means indicates a motion vector search range to be detected by the motion vector detection means, based on the motion vector number corrected by the correction means.
The correction means includes means for correcting the number corresponding to a classification containing a motion vector with the vector value of (0, 0), among motion vector numbers stored in the motion vector frequency storage means. Since moving images generally contain many still regions, the vector value of a motion vector detected from each divided region by the motion vector detection means is often expressed by (0, 0). If the number of motion vectors at (0, 0)is not corrected, the situation may occur where the center of the search range of vector values of the motion vector is always set to (0, 0). The above-mentioned correction means can prevent such a situation and can establish a suitable search range. Moreover, the correction means includes means for smoothing the motion vector numbers classified and stored in said motion vector frequency storage means within close vector value ranges by classification.
Thus, the correction means can remove a local effect on the detection results of a motion vector and can establish a suitable search range from the whole situation.
As described above, in the motion vector detection device having the correction means, the indication means indicates the motion vector search range so as to center the vector value corresponding to a classification having the largest motion vector among classifications containing the motion vector number corrected by the correction means.
The indication means indicates a motion vector value search range based on numbers with a larger value than a predetermined threshold value among the motion vector numbers corrected by the correction means.
In the motion vector detection device, the time interval between the reference frame and the current frame may differ for each frame. In this case, the indication means indicates a motion vector value search range according to a time interval between the reference image data and image data for the current frame.
Thus, even if the time interval between the reference image data and the image data for a current frame is different from each frame, the search range of vector values of a motion vector can be always set to a suitable range.
When the time interval between a reference frame and image data in a current frame is different every frame, the reference image data may come before and after image data for the current frame in input order. In this case, the motion vector frequency storage means includes means for adjusting vector values of motion vectors detected by the motion vector detection means to provide a different sign when the reference image data comes before or after image data for the current frame.
In the motion vector detection device, the motion vector detection means can detect plural motion vectors from each of divided regions. In this case, the motion vector frequency storage means assigns weights to motion vector numbers detected from each divided region by the motion vector detection means and then stores the weighted motion vector numbers.
In order to accomplish the above-mentioned object, the motion vector detecting method comprises a vector motion detection step of dividing image data for a current frame into predetermined regions, matching the image data of the current frame with reference image data every divided region; and detecting a motion vector with a vector value within a search range externally indicated; a motion vector distribution creation step of creating a distribution where motion vectors detected from each divided region in the motion vector detection step are classified every range of predetermined vector values; and an indication step of indicating a motion vector value search range to be detected in the motion vector detection, based on the distribution created in the distribution creation step.